package com.nju.demos;

public class MaxSubSequenceSum {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int a[] = { -2, 11, -4, 13, -5, 2, -5, -3, 12, -9 };
		maxSubSequenceSum(a, a.length);
	}

	/*
	 * 分治法实现，算法复杂度O(n*log(n)) 
	 * 分：使用二分法进行分段 
	 * 治：详细算法见maxSubSequenceSum内描述，简述为：
	 * 全段最大子序列为以下三者中的最大值 
	 * 左段最大子序列和 
	 * 右段最大子序列和 
	 * 左段最大含右边界子序列和最大值和右段最大含左边界子序列和最大值之和
	 */
	public static void maxSubSequenceSum(int a[], int len) {
		int result = maxSubSequenceSum(a, 0, len - 1);
		System.out.println("result: " + result);
	}

	/*
	 * 求序列某段子序列中子序列和最大值
	 */
	public static int maxSubSequenceSum(int a[], int left, int right) {
		int center;
		int leftMaxSum;
		int rightMaxSum;
		int maxLeftBorderSum;
		int maxRightBorderSum;

		/* 递归终止条件 */
		if (left == right) {
			return a[left];
		}

		/* 分治法递归开始，取中点二分处理 */
		center = (left + right) >> 1; /* center = (left + right) / 2; */

		/* 递归求左右子序列段中最大子序列和 */
		leftMaxSum = maxSubSequenceSum(a, left, center);
		rightMaxSum = maxSubSequenceSum(a, center + 1, right);

		maxRightBorderSum = maxRightBoderSubSequenceSum(a, left, center);
		maxLeftBorderSum = maxLeftBoderSubSequenceSum(a, center + 1, right);

		/*
		 * 二分后的最大值有三个： 
		 * 1、leftMaxSum，左段最大子序列和 
		 * 2、rightMaxSum，右段最大子序列和
		 * 3、maxLeftBorderSum+maxRightBorderSum，左段最大含右边界子序列和最大值和右段最大含左边界子序列和最大值，二者之和
		 * 这三者中的最大值即为分段前的最大子序列和
		 * 
		 * 分治算法核心部分，解决分治后结果归并问题，具体分析：
		 * 这是对分段后的子序列的一种划分，有三种，只需分别求出各种的最大值然后在三者之间取一个最大值即可：
		 * 1、子序列全在左段，最大子序列和为leftMaxSum 
		 * 2、子序列全在右段，最大子序列和为rightMaxSum
		 * 3、子序列跨左右段，最大字序列和为maxLeftBorderSum+maxRightBorderSum
		 */
		return tmax(leftMaxSum, rightMaxSum, maxLeftBorderSum
				+ maxRightBorderSum);
	}

	/*
	 * 某段字序列中，含左边界元素的字序列和中的最大值，maxSubSequenceSum中使用
	 */
	public static int maxLeftBoderSubSequenceSum(int a[], int left, int right) {
		int i;
		int sum = 0;
		int maxSum = a[left];
		for (i = left; i <= right; i++) {
			sum += a[i];
			if (sum > maxSum) {
				maxSum = sum;
			}
		}
		return maxSum;
	}

	/*
	 * 某段字序列中，含右边界元素的字序列和中的最大值，maxSubSequenceSum中使用
	 */
	public static int maxRightBoderSubSequenceSum(int a[], int left, int right) {
		int i;
		int sum = 0;
		int maxSum = a[right];
		for (i = right; i >= left; i--) {
			sum += a[i];
			if (sum > maxSum) {
				maxSum = sum;
			}
		}
		return maxSum;
	}

	/*
	 * 求出三个数中的最大值
	 */
	public static int tmax(int a, int b, int c) {
		int result = a;
		if (result < b) {
			result = b;
		}
		if (result < c) {
			result = c;
		}
		return result;
	}
}
